//
// Created by xili on 2024/9/2 19:29.
// GO BIG OR GO HOME.
//
#include "leetcode.h"

class Solution {
public:
    vector <string> topKFrequent(vector <string> &words, int k) {
        auto cmp = [](const pair<string, int> &a, const pair<string, int> &b) {
            return a.second == b.second ? a.first < b.first : a.second > b.second;
        };
        unordered_map<string, int> ump;
        for (auto &v: words) {
            ump[v]++;
        }
        priority_queue < pair < string, int >, vector < pair < string, int >>, decltype(cmp) > pq(cmp);
        for (auto &it: ump) {
            pq.emplace(it);
            if (pq.size() > k) {
                pq.pop();
            }
        }
        vector <string> ret(k);
        for (int i = k - 1; i >= 0; i--) {
            ret[i] = pq.top().first;
            pq.pop();
        }
        return ret;
    }
};